Reference counting refers to a technique for tracking a number of references (i.e., pointers or handles) to a particular resource of a computer system. For example, a portion of memory in system RAM (Random Access Memory) may be allocated to store an instantiation of an object associated with an application. A handle to that object is stored in a variable and a reference count for the object is set to one. The reference count indicates that there is one variable in memory that refers to the object via the handle. If the handle is copied into another variable, then the reference count may be incremented. If the variable storing the handle is overwritten, then the reference count may be decremented. Any resource having a reference count of zero can be safely reallocated because there is no longer any active reference that points to that resource.
Some systems may include a resource that is implemented as a block device. A block device includes a number of blocks of non-volatile memory. Hard disk drives, optical drives, and solid state drives are all examples of hardware devices that can be implemented as a block device. When an operating system allocates a block of the block device to a particular process or processes, the operating system also typically allocates space in system RAM to store reference counters associated with the block.
Some contemporary systems may implement a hypervisor on a node along with one or more virtual machines. Virtual machines are logical devices that emulate shared hardware resources connected to the node. In other words, two or more virtual machines may be implemented on the same node and configured to share common resources such as a processor, memory, or physical storage devices. The hypervisor may implement one or more virtual storage devices that emulate a real storage device for the virtual machines. The virtual storage device may contain a plurality of blocks of memory that are stored in one or more physical storage devices connected to the node. Contiguous blocks on the virtual storage device may refer to non-contiguous blocks on one or more physical storage devices. When reference counting is used in conjunction with the virtual storage devices, the reference counters associated with the virtual storage device may be stored in the RAM.
It will be appreciated that many systems that implement virtual machines include a plurality of nodes connected via a network, each node including one or more virtual machines. In such systems, multiple nodes may include virtual storage devices that can refer to the same blocks of data in the physical storage devices coupled to the nodes. It will be appreciated that implementing a garbage collection algorithm using reference counters in such systems may be difficult because one node may keep a reference counter for a block of a physical device that is also mapped to a block of another virtual storage device on another node. Thus, in order to ensure that a block of memory in the physical storage device is not prematurely overwritten, the nodes will need to implement a protocol for determining when blocks of the physical storage devices may be deallocated. Alternatively, a block of memory in the physical storage device can be restricted to only be mapped to a single virtual storage device, but such a restriction may make the system inefficient by requiring multiple redundant copies of a block of data when two or more virtual storage devices refer to the same block of data. Thus, there is a need for addressing this issue and/or other issues associated with the prior art.